import java.util.*;;
/**
 * 
 * 寻找最大价值的矿堆
 * 
 * 题目描述

给你一个由 '0' (空地)、'1' (银矿)、'2'(金矿) 组成的的地图，矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。

假设银矿价值1，金矿价值2 ，请你找出地图中最大价值的矿堆并输出该矿堆的价值。

输入描述
地图元素信息如：

22220
00000
00000
11111
地图范围最大 300*300
0 ≤ 地图元素 ≤ 2
输出描述
矿堆的最大价值

用例
输入	22220
00000
00000
01111
输出	8
说明	无
输入	22220
00020
00010
01111
输出	15
说明	无
输入	20000
00020
00000
00111
输出	3
说明	无

 */

 /**
  * 
  题目解析
本题可以使用“广度优先搜索”解题。

首先，根据输入得到一个地图矩阵。

然后，定义一个visited集合，用于记录访问过的点的坐标，或者将访问过的点赋值为0，避免一些点被二次访问。

之后，开始遍历矩阵的每一个元素，如果

该元素的值>0（代表有价值）
该元素位置未被访问过
那么就可以从该点向上、下、左、右四个方向开始广搜。

本题不建议使用深度优先搜索（基于递归），因为本题的地图数量级300*300，使用深度优先搜索可能会Stack Overflow异常。或者使用基于自定义栈的深度优先搜索。比如博客中C语言的解法。

本题的输入获取是不定行输入获取，具体可以参考：

ACM模式不定行输入获取_华为od机考acm模式是什么意思-CSDN博客
https://blog.csdn.net/qfc_128220/article/details/132385403
  */
public class 寻找最大价值的矿堆 {
    
    static ArrayList<char[]> matrix = new ArrayList<>();
    static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in).useDelimiter(",\n");
 
        while (sc.hasNextLine()) {

            String line = sc.nextLine();
            if(line.equals("")) break;

            matrix.add(line.toCharArray());
        }
 
        int max = 0;
 
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix.get(i).length; j++) {
                if (matrix.get(i)[j] != '0') {
                    max = Math.max(max, bfs(i, j));
                }
            }
        }
 
        System.out.println(max);
    }
 
    public static int bfs(int i, int j) {
        int sum = matrix.get(i)[j] - '0';
        matrix.get(i)[j] = '0';
 
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{i, j});
 
        while (!queue.isEmpty()) {
            int[] pos = queue.removeFirst();
 
            int x = pos[0];
            int y = pos[1];
 
            for (int[] offset : offsets) {
                int newX = x + offset[0];
                int newY = y + offset[1];
 
                if (newX >= 0 && newX < matrix.size() && newY >= 0 && newY < matrix.get(0).length && matrix.get(newX)[newY] != '0') {
                    sum += matrix.get(newX)[newY] - '0';
                    matrix.get(newX)[newY] = '0';
                    queue.add(new int[]{newX, newY});
                }
            }
        }
 
        return sum;
    }
}
